/**
 * 快速排序实现
 * @param {number[]} arr
 * @returns {number[]}
 */
function quickSort(arr) {
  if (arr.length <= 1) return arr;
  const pivot = arr[Math.floor(arr.length / 2)];
  const left = [];
  const right = [];
  const equal = [];
  for (let num of arr) {
    if (num < pivot) left.push(num);
    else if (num > pivot) right.push(num);
    else equal.push(num);
  }
  return [...quickSort(left), ...equal, ...quickSort(right)];
}

// 测试用例
const testCases = [
  [],
  [1],
  [5, 3, 8, 4, 2],
  [10, 9, 8, 7, 6, 5],
  [1, 2, 3, 4, 5],
  [3, 3, 3, 3],
  [5, -1, 0, 2, -3, 8]
];

for (const arr of testCases) {
  console.log(`原数组: [${arr}] => 排序后: [${quickSort(arr)}]`);
}